import java.util.Map;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-04-02
 * Time:12:01
 */
public class TestDemo {
    //420. 强密码检验器
    // 如果一个密码满足下述所有条件，则认为这个密码是强密码：
    //由至少 6 个，至多 20 个字符组成。
    //至少包含 一个小写 字母，一个大写 字母，和 一个数字 。
    //同一字符 不能 连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 如果满足其他条件也可以算是强密码)。
    //给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。
    //在一步修改操作中，你可以：
    //插入一个字符到 password ，
    //从 password 中删除一个字符，或
    //用另一个字符来替换 password 中的某个字符。

    //思路
    // 长度 <6 ，步数=缺失类型和缺失长度取大者。
    //长度 (6,20)，这时候我们不需要低效的插入和删除来处理连续字符，直接替换步数就等于处理连续字和缺失类型取大者。
    //比较负载的是 >20，我们需要知道优先级，一样优先处理连续数组。
    //1、 最难理解的主要是 长度 > 20 的时候应该怎么办
    //2、长度大于20删除是有优先级别的：
    //- 例: aaaabaaaA1bcdefghixyz (21位 ： 有大小写和数字 唯一冲突是 aaaa 和 aaa)
    //- 目前的删除是只需要一次，之后通过替换即可解决，可以发现 删除aaaa 中任意一个都是无效的删除，因为还是需要替换两次，但是删除 aaa中的一个就能节省一次替换。
    //- 掌握上述信息不难发现，首先应该删除刚好是3的倍数的连续串，因为删除一个确确实实节省了一次替换，其次要删除3的倍数余1的连续串，这个删除2个才能节省一次，最后就是3个3个的删除，大家都一样。

    public static void main1(String[] args) {
        String s = "1337C0d3";
        System.out.println(strongPasswordChecker(s));
    }

    public static int strongPasswordChecker(String password) {
        int length = password.length();
        int lowerCase = 0;
        int upperCase = 0;
        int number = 0;
        for (int i = 0; i < length; i++) {
            if (password.charAt(i) >= 'a' && password.charAt(i) <= 'z') {
                lowerCase = 1;
            } else if (password.charAt(i) >= 'A' && password.charAt(i) <= 'Z') {
                upperCase = 1;
            } else if (password.charAt(i) >= '0' && password.charAt(i) <= '9') {
                number = 1;
            }
        }
        int sum = lowerCase + upperCase + number;
        if (length < 5) {
            //不管原来什么密码都可以通过插入解决
            return 6 - length;
        }
        if (length == 5) {
            if (sum >= 2) {
                return 1;
            } else {
                return 2;
            }
        }
        //6-20
        //统计可以替换的次数
        int res = 0;
        if (length <= 20) {//采用替换即可
            char last = password.charAt(0);
            int count = 1;
            for (int i = 1; i < length; i++) {
                if (password.charAt(i) == last) {
                    count++;
                } else {
                    //只有三个或三个以上连续相同才算入需要替换的次数
                    res += count / 3;
                    last = password.charAt(i);
                    count = 1;
                }
            }
            //最后3个字母相同的情况
            res += count / 3;
            return Math.max(res, 3 - sum);
        }
        //>20删除和替换
        int[] tmp = {0, 0, 0};
        char last = password.charAt(0);
        int count = 1;
        for (int i = 1; i < length; i++) {
            if (password.charAt(i) == last) {
                count++;
            } else {
                if (count >= 3) {
                    tmp[count % 3]++;
                }
                res += count / 3; 
                last = password.charAt(i);
                count = 1;
            }
        }
        //最后的字母相同的情况
        if (count >= 3) {
            tmp[count % 3]++;
        }
        res += count / 3;
        //必须删除的个数
        int del = length - 20;
        if (tmp[0] > del) {
            return del + Math.max(res - del, 3 - sum);
        } else if (tmp[0] + 2 * tmp[1] > del) {
            return del + Math.max(res - tmp[0] - (del - tmp[0]) / 2, 3 - sum);
        } else {
            return del + Math.max(res - tmp[0] - tmp[1] - (del - tmp[0] - 2 * tmp[1]) / 3, 3 - sum);
        }
    }
}
